增强学习

增强学习的思想来自于对自然学习的观察，比如人类获取知识的主要途径就是通过与环境的交互iteractions。增强学习问题研究what to do，即如何从situations映射到actions，从而最大化一个数值形式的reward。本质上看，这是个闭环问题closed-loop，因为actions会影响后来的输入，即situations。最有趣，也是最有挑战性的一点是，actions不光影响即时的reward，也会影响后续所有的rewards。

增强学习不同于当前机器学习领域研究最多的监督学习。监督学习从标注训练集中学习，每个样本是一个situation和正确的action的集合。比如常见的分类任务中，给定一幅图像（situation），算法需要给出对应的分类（action）。监督学习的目标是实现正确的泛化，即能够正确地应对训练集中未出现过的situation。但是对于交互式的问题，监督学习并不适用。因为在交互问题中，算法无法得到足够而正确的标注样本进行训练。agent必须从自身的经验中学习。

增强学习也不同于无监督学习。无监督学习通常关注于从未标注数据中寻找隐藏的分布结构。

因此，增强学习是与监督学习和无监督学习并列的关系。

exploration-exploitation dilemma

增强学习要面临的挑战是探索（exploration）和开发（exploitation）之间的trade-off。为了获得大量reward，agent必须偏向于选择那些它过去尝试过，并被证明能够高效产生reward的actions。但是与此同时，为了探索这些actions，agent也必须尝试那些之前没有选择过的action。因此，agent必须exploit已知的内容以获取最大reward，也必须保证一定的explore，以助于将来做出更好的action选择。

###
增强学习的另一个特点是，它明确地从全局角度考虑了一个目标导向的agent与未知环境的交互问题。

增强学习基于一个完整的、交互式的、目标导向的agent。agent有明确的目标，能够感知他们所在的环境的某些方面，并且能够选择actions来影响环境。因为增强学习涉及了规划的问题，所以agent必须考虑规划（planning）和实时动作选择（real-time action selection）之间的相互影响，以及如何获取和改善环境模型。

这和许多其他只关注子问题的方法不同。（可能意思是说不是general的）。比如监督学习并没有明确地解释学习到的能力为什么会work。(挖个坑，等理解深点再来补充)

增强学习的组成元素

policy

给定一个时间状态，policy决定了agent会做出什么行动。粗略地讲，policy将感知到的环境状态映射到要采纳的动作。某种程度上有点类似生物学中的条件反射。policy可能是简单的映射函数或者数值表，也可能是复杂的搜索过程。policy是一个agent的核心，决定了agent的行为。一般，policy都是有随机性的（stochastic）。（可能是为了保证探索和开发之间的平衡）

reward

reward信号定义了增强学习的目标。每个时间节点，环境都会给agent一个相应作为reward。而agent唯一的目标就是在长时运行中最大化reward总和。所以说，reward是agent改变policy的动力。

value function

reward信号表示在某个时刻的感知中，什么是有益的；而value function则是从长远的角度考虑。粗略地讲，某个时刻的value，等于该状态的reward，累积后续所有预期状态的reward，得到的reward总和。所以，value function给agent带来了长远的规划能力。

environment model（optional）

env model是对环境的建模，实现如下功能：给定一个state和action，model会反馈出下一个state和reward。

样例 Tic-Tac-Toe

Tic-Tac-Toe是一个简单的棋盘类游戏，规则有点类似五子棋。两个棋手对战，轮流放棋子，在一个三乘三的棋盘中，首先完成一行、一列或一条对角线的一方获胜。

看起来很简单的游戏却很难用传统的方法来解决。比如动态规划需要知道对手的完整表述，包括对手在某个状态下采取什么行动的概率。这在实际中是不可能得到的。

进化方法（evolutionary method）直接搜索policy space，寻找一个胜率最高的policy。例如，遗传算法（genetic algorithm）会维持并进化一个population，在多次迭代中搜索最优的policy。

基于value function的方法则采用另外一种思路。首先，建立一个数表，代表所有可能的states和它们对应的胜利概率估计。比如，某个状态中，有一行全部被agent的棋子占据，则该状态对应的value就是1；如果全部被对手的棋子占据，则value为0。除了这两种极端情况，其他状态的初始value被设定为0.5。这个表就是value function的具体形式。在游戏中，我们观察一次行动（即放置一颗棋子到棋盘上任意空位处）可能会产生的states（不同的棋子摆放格局）和它们对应的表中的value。大多数情况下，我们会依据贪婪的原则选择value最大的那个state对应的行动，称作greedy move；但是有的时候也会随机地选择行动，称作exploratory move。

在greedy move之后，需要更新move之前的状态的value。设s表示move前状态，s’表示move之后的状态，V(:)表示value function，$\alpha$为学习率：
$$V(s) = V(s) + \alpha[V(s’) - V(s)]$$

为了评估一个policy，进化方法会先固定该policy参数，然后多次模拟对战，取胜利的频率作为该policy胜率的无偏估计。但是每次更新policy都需要在很多次对战之后，并且只利用了每次对战的结果信息，忽视了对战中发生了什么。

相反的，增强学习评估对战中的每个状态。这两种方法都实现了对policy space的搜索，但是后者利用了更多信息，也更加合理。

从本例中，还能看到增强学习的几个关键特征。首先是，从与环境的交互（对战）中学习。其次，有一个清晰的目标，考虑、预见了每次行动对未来的影响。所以，本例中的一个简单的增强学习agent就可能能够通过多步move来给对手设置陷阱。